package com.platform.modules.alg.alglib.hdu1166;

public class Hdu1166 {
    public String output = "";
    private final int maxn = 55555;
    private int a[] = new int[maxn];
    private int sum[] = new int[maxn << 2];

    // 更新和值
    void PushUP(int rt) {
        sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }

    // 构建线段树
    void build(int l, int r, int rt) {
        if (l == r) {
            sum[rt] = a[l];
            return;
        }
        int m = (l + r) >> 1;
        build(l, m, rt << 1);
        build(m + 1, r, rt << 1 | 1);
        PushUP(rt);
    }

    // 单点更新
    void update(int p, int add, int l, int r, int rt) {
        if (l == r) {
            sum[rt] += add;
            return;
        }
        int m = (l + r) >> 1;
        if (p <= m) update(p, add, l, m, rt << 1);
        else update(p, add, m + 1, r, rt << 1 | 1);
        PushUP(rt);
    }

    // 区间查询
    int query(int L, int R, int l, int r, int rt) {
        if (L == l && r == R)//判断条件为相等
            return sum[rt];
        int m = (l + r) >> 1;
        if (R <= m)
            return query(L, R, l, m, rt << 1);
        else if (L > m)
            return query(L, R, m + 1, r, rt << 1 | 1);
        else return query(L, m, l, m, rt << 1) + query(m + 1, R, m + 1, r, rt << 1 | 1);
    }

    public String cal(String input) {
        int n;
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]); // 10
        String[] nums = line[1].split(" ");
        for (int x = 1; x <= n; x++)
            a[x] = Integer.parseInt(nums[x - 1]);
        build(1, n, 1);
        int count = 2;
        while (true) {
            String[] command = line[count++].split(" ");
            if (command[0].equals("End")) break;
            int i = Integer.parseInt(command[1]);
            int j = Integer.parseInt(command[2]);
            if (command[0].equals("Query")) {
                output += query(i, j, 1, n, 1) + "\n";
            } else if (command[0].equals("Sub")) {
                update(i, -j, 1, n, 1);
            } else {
                update(i, j, 1, n, 1);
            }
        }
        return output;
    }
}
